package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2022/2/23.<br><br>
 *
 * 简单：x 的平方根
 */
public class Topic69 {

    public static void main(String[] args) {
        Topic69 instance = new Topic69();

        System.out.println(instance.mySqrt(4));
        System.out.println(instance.mySqrt(3));
        System.out.println(instance.mySqrt(8));
    }

    public int mySqrt(int x) {
        if(x == 1 || x == 0) {
            return x;
        }

        int low = 1;
        int high = x;
        int middle = 0;

        while (low <= high) {
            middle = (low + high) / 2;
            int div = x / middle;
            if(div < middle) {
                high = middle - 1;
            }
            else if(div > middle) {
                low = middle + 1;
            }
            else {
                return middle;
            }
        }

        return high;
    }
}
